import java.util.*;

public class Day2 {
    public static void main(String[] args) {
    }
    public static void main1(String[] args) {
        StringBuilder path = new StringBuilder();
        path.append('(');
        path.length();

        Map<Character,Integer> map = new HashMap<>();
        map.getOrDefault('(',0);
        path.deleteCharAt(0);
        Stack<Character> stack = new Stack<>();

    }

    //22.括号生成-暴力不剪纸
    List<String> ret = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    Stack<Character> stack = new Stack<>();
    public List<String> generateParenthesis(int n) {
        int l = 0;
        int r = 0;
        boolean check = true;
        dfs(n,l,r,check);
        return ret;
    }
    //难点-匹配括号
    public void dfs(int n,int left,int right,boolean check) {
        if(path.length() == 2*n) {
            if(left == right && check) {
                ret.add(path.toString());
            }
            return;
        }
        path.append('(');
        left++;
        dfs(n,left,right,check);
        //回溯
        if(path.charAt(path.length()-1) == ')') right--;
        else left--;
        path.deleteCharAt(path.length()-1);

        path.append(')');
        right++;
        if(left < right) check = false;
        dfs(n,left,right,check);
        //回溯
        if(path.charAt(path.length()-1) == ')') right--;
        else left--;
        path.deleteCharAt(path.length()-1);
    }
    //剪枝
    /*List<String> ret = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    Stack<Character> stack = new Stack<>();
    int left = 0;
    int right = 0;
    int n = 0;
    public List<String> generateParenthesis(int _n) {
        n = _n;
        dfs();
        return ret;
    }

    public void dfs() {
        if(right == n) {
            ret.add(path.toString());
            return;
        }
        if(left < n) {
            path.append('(');
            left++;
            dfs();
            //回溯
            path.deleteCharAt(path.length()-1);
            left--;
        }
        if(right < left) {
            path.append(')');
            right++;
            dfs();
            //回溯
            path.deleteCharAt(path.length()-1);
            right--;
        }
    }*/

    //77.组合
   /* List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int n;
    int k;
    public List<List<Integer>> combine(int _n, int _k) {
        n = _n;
        k = _k;
        dfs(1);
        return ret;
    }
    public void dfs(int pos) {
        if(path.size() == k) {
            ret.add(new ArrayList(path));
            return;
        }
        for(int i=pos;i <= n;i++) {
            path.add(i);
            dfs(i+1);
            //回溯
            path.remove(path.size()-1);
        }
    }*/

    //494.目标和-无剪枝写法
    int path1;
    int count;
    int target;
    public int findTargetSumWays(int[] nums, int _target) {
        target  =_target;
        dfs(nums,0);
        return count;
    }
    public void dfs(int[] nums,int pos) {
        if(pos == nums.length) {
            if(path1 == target) {
                count++;
            }
            return;
        }
        path1+=nums[pos];
        dfs(nums,pos+1);
        path1-=nums[pos];//回溯

        path1-=nums[pos];
        dfs(nums,pos+1);
        path1+=nums[pos];//回溯
    }

}
